#ifndef BINARYTREEWINDOW_H
#define BINARYTREEWINDOW_H

#include <QMainWindow>
#include <QVBoxLayout>
#include <QHBoxLayout>
#include <QTextEdit>
#include <QLineEdit>
#include <QPushButton>
#include <QLabel>
#include <QGroupBox>
#include <QMessageBox>
#include <QComboBox>
#include <QWidget>
#include <QPainter>
#include <QScrollArea>
#include <QScrollBar>
#include <QTimer>
#include "intarray.h"  // 包含共享的IntArray

struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

// 自定义队列替代std::queue
class TreeNodeQueue {
private:
    struct QueueNode {
        TreeNode* data;
        QueueNode* next;
        QueueNode(TreeNode* val) : data(val), next(nullptr) {}
    };

    QueueNode* m_front;
    QueueNode* m_rear;
    int m_size;

public:
    TreeNodeQueue() : m_front(nullptr), m_rear(nullptr), m_size(0) {}

    ~TreeNodeQueue() {
        while (!empty()) {
            pop();
        }
    }

    void push(TreeNode* value) {
        QueueNode* newNode = new QueueNode(value);
        if (m_rear == nullptr) {
            m_front = m_rear = newNode;
        } else {
            m_rear->next = newNode;
            m_rear = newNode;
        }
        m_size++;
    }

    void pop() {
        if (empty()) return;

        QueueNode* temp = m_front;
        m_front = m_front->next;
        if (m_front == nullptr) {
            m_rear = nullptr;
        }
        delete temp;
        m_size--;
    }

    TreeNode* front() const {
        return empty() ? nullptr : m_front->data;
    }

    bool empty() const {
        return m_front == nullptr;
    }

    int size() const {
        return m_size;
    }
};

class TreeVisualizationWidget : public QWidget
{
    Q_OBJECT

public:
    explicit TreeVisualizationWidget(QWidget *parent = nullptr) :
        QWidget(parent), root(nullptr), m_treeWidth(0), m_treeHeight(0), m_nodePointers(nullptr), m_nodeCount(0),
        m_currentTraverseNode(nullptr), m_currentTraverseNodeIndex(-1) {}

    ~TreeVisualizationWidget() {
        if (m_nodePointers != nullptr) {
            delete[] m_nodePointers;
        }
    }

    void setRoot(TreeNode* rootNode) {
        root = rootNode;
        calculateTreeDimensions();
        update();
    }

    QSize getTreeSize() const { return QSize(m_treeWidth, m_treeHeight); }

    // 遍历可视化相关方法
    void startTraversal(const QVector<TreeNode*>& order);
    void nextTraversalStep();
    void resetTraversal();
    bool isTraversing() const { return m_currentTraverseIndex >= 0 && m_currentTraverseIndex < m_traverseOrder.size(); }

    // 获取当前遍历节点的位置
    QPoint getCurrentTraverseNodePosition() const;

signals:
    void traversalStepCompleted(const QString& currentResult);

protected:
    void paintEvent(QPaintEvent* event) override;

private:
    void calculateTreeDimensions();
    void calculateNodePositions();
    void drawTree(QPainter& painter);
    void drawThreeCellNode(QPainter& painter, TreeNode* node, int x, int y);
    void drawPointerLine(QPainter& painter, int startX, int startY, int endX, int endY);
    void drawNullPointer(QPainter& painter, int startX, int startY, bool isLeft);

    int getTreeHeight(TreeNode* node);
    int getTreeWidth(TreeNode* node);
    void calculateSubtreeWidth(TreeNode* node, int level, int& maxWidth);

    TreeNode* root;
    int m_treeWidth;
    int m_treeHeight;

    // 存储节点位置信息
    IntArray m_nodePositionsX;
    IntArray m_nodePositionsY;
    TreeNode** m_nodePointers;
    int m_nodeCount;

    // 遍历可视化相关成员
    TreeNode* m_currentTraverseNode;
    QVector<TreeNode*> m_traverseOrder;
    int m_currentTraverseIndex;
    int m_currentTraverseNodeIndex;
};

class BinaryTreeWindow : public QMainWindow
{
    Q_OBJECT

public:
    BinaryTreeWindow(QWidget *parent = nullptr);
    ~BinaryTreeWindow();

signals:
    void returnToMainMenu();

private slots:
    void onInputData();
    void onInsert();
    void onTraverse();
    void onClear();
    void onGenerateRandom();
    void onReturnToMainMenu();
    void onTraversalStepCompleted(const QString& currentResult);

private:
    void setupUI();
    void updateDisplay();
    void clearTree(TreeNode* node);
    void preorderTraversal(TreeNode* node, QVector<TreeNode*>& result);
    void inorderTraversal(TreeNode* node, QVector<TreeNode*>& result);
    void postorderTraversal(TreeNode* node, QVector<TreeNode*>& result);
    void levelOrderTraversal(TreeNode* node, QVector<TreeNode*>& result);
    TreeNode* buildTreeFromLevelOrder(const IntArray& values);
    int getTreeHeight(TreeNode* node);

    // 替换std::max的辅助函数
    int max(int a, int b) { return a > b ? a : b; }

    // 替换随机数生成的函数
    int randomInt(int min, int max);

    // 滚动到指定节点位置
    void scrollToNodePosition(const QPoint& nodePos);

    TreeNode* m_root;
    int m_size;

    QTextEdit *m_display;
    QComboBox *m_traverseCombo;

    TreeVisualizationWidget *m_visualizationWidget;
    QScrollArea *m_scrollArea;

    // 遍历相关成员
    QTimer *m_traverseTimer;
    QString m_currentTraverseResult;
    bool m_isTraversing;
    int m_traverseSpeed;
};

#endif // BINARYTREEWINDOW_H
